Keep and carry on.
post @ 2023-12-23

信息安全数学基础

课程实验报告

实验报告(四)

系 别: 网络空间安全系

班 级: secret!

姓 名: secret!

学 号: secret!

实验时间: 2023年11月15日

指导老师: secret!

湖南大学信息科学与工程学院

  1. 实验内容

  1. 实验目标

理解指数定义和求解思路,理解原根存在判断条件和求解过程,用c++编程实现,并在求解原根时优化算法并测试电脑计算性能。

  1. 实验原理

1.指数

2.原根

  1. 实验设计

实验共分为1个主函数和4个自定义函数。其中,主函数负责部分基本变量定义、判断模数p是否为奇素数以及程序的输入和输出,isOddPrime函数是辅助函数判断模数p是否为奇素数的程序执行前提,Euler函数也是辅助函数求解模数p的欧拉函数在求解指数后可以判断该指数是否为原根,也可在求原根优化时作为循环条件区间值,Exp函数是解答第一问的求指数函数,Prim函数是解答第二问的求模数p所有原根

  1. 定义变量和函数

主函数:

底数:a

模数:p

欧拉函数:elr

指数:ord

存放所有原根的数组roots

isOddPrime函数:

函数参数传入的模数:p

函数返回bool类型:true/false

Euler函数:

函数参数传入的模数:p

计数器:cnt

迭代递增指数:e

Exp函数:

函数参数传入的底数和模数:a和p

迭代递增计数器和返回值:e

存放余数的中间变量:result

Prim函数:

函数参数传入的模数:p

存放所有原根的数组stl容器:prim

欧拉函数:euler

迭代递增的底数g

判断是否为原根bool类型:isPrim

  1. 主函数

主函数负责部分基本变量定义、判断模数p是否为奇素数以及程序的输入和输出。首先读入底数a和模数p,通过调用isOddPrime函数判断p是否为奇素数,如果不是,则直接返回0并结束程序。

然后,通过调用Euler函数计算模p的欧拉函数值,并将结果赋给变量elr。这个中间结果在后面计算中多次用到,所以可以先提前计算出来。打印提示信息和elr结果。

接下来,通过调用Exp函数计算整数a模p的指数,并将结果赋给变量ord。打印提示信息和ord结果。

然后,通过调用Prim函数计算模p的所有原根,并将结果存储在名为roots的vector容器中。然后,使用for循环遍历roots容器中的每个元素,并使用输出流cout打印出每个原根的值。

  1. isOddPrime函数

isOddPrime函数是辅助函数判断模数p是否为奇素数

函数参数传入模数p,首先进行两个条件判断:如果p小于等于1,或者p是偶数,则返回false,因为偶数不可能是素数。 如果以上条件都不满足,那么进入循环。

循环从i=3开始,每次迭代增加2,因为偶数已经在前面的条件判断中排除了。循环条件是i * i <= p,即i的平方小于等于p。

在循环体中,判断p是否能被小于等于其平方根的奇数整除,来确定p是否为奇素数。如果能整除,则p不是素数,返回false。如果循环结束后仍然没有找到能整除p的数,则p是素数,返回true。

  1. Euler函数

Euler函数也是辅助函数求解模数p的欧拉函数在求解指数后可以判断该指数是否为原根,也可在求原根优化时作为循环条件区间值。

函数参数传入模数p,首先声明一个整数变量count,用于计数满足条件的数值。然后,通过一个for循环遍历从1到p-1的所有整数。

在循环体中,通过遍历从1到p-1的整数,计算与p互质的数值的个数,从而得到p的欧拉函数值。具体的通过调用库函数中的__gcd函数计算i和p的最大公约数。如果最大公约数等于1,说明i和p互质,即没有共同的因子,满足欧拉函数的定义。此时,将count加1。

循环结束后,count记录了满足条件的数值的个数,即p的欧拉函数值。将count作为函数的返回值。

  1. Exp函数

Exp函数是解答第一问的求指数函数,程序设计思想参考指数的定义。

函数参数传入底数a和模数p。函数首先声明一个整数变量e,用于记录指数的值,初始值为1。然后,声明一个整数变量result,用于存储a对模p的中中间结果。

通过使用循环来计算a的幂,直到结果等于1为止。在每次循环中,将结果乘以a并对p取模,同时记录循环的次数。最后返回循环的次数,也就是指找到最小的正整数e,使得a^e ≡ 1 (mod p)。

  1. Prim函数

Prim函数是解答第二问的求模数p所有原根,上图展示的优化后的算法,优化过程如下:

如果按照原根存在的充要条件实现需要2个函数和3重for循环。首先PrimeQ函数求解整数p-1的所有素因子,q数组容器存放所有的素因子,PrimeQ函数内部通过双重for循环,外层for循环判断i是否能被p整除,内层for循环再判断因子是否是素数,如果满足就向容器中插入p-1/i

Prime1函数计算所有原根。使用3重for循环,第一层for循环遍历2到小于p的整数,第二层for循环遍历计算的p-1/i,将其依次作为指数,内层for循环累乘p-1/i次。

由此可见2个弊端:3层for循环是立方级别的运算,时间复杂度很高;muti累乘很容易超过数据类型的范围。

优化:考虑原根的性质,即它是指数且小于欧拉函数确定遍历范围,以及原根定义是指数等于欧拉函数确定判断条件;并且考虑用long long存放数据类型。合理灵活运用之前的两个函数:Euler函数的结果和Exp求指数函数。优化后仅用两重循环,降低时间复杂度。

函数接受一个长整型参数p,表示模数。它使用循环来遍历从2到p-1的所有整数,判断每个整数是否为模p的原根。

函数首先声明一个vector类型的变量prim,用于存储找到的所有原根。

接下来,通过一个for循环遍历从2到p-1的所有整数,用变量g表示当前整数,对每个整数进行指数计算调用Exp函数,若结果等于欧拉函数则为原根,插入容器中保存。

最后,将存储原根的prim容器作为函数的返回值。

  1. 实验结果
  2. 教材例5.1.1

题目:教材例5.1.1

输入解释:

依次输入:2 7,分别表示底数a和模数p

输出结果:

模p的欧拉函数是:6

整数a模p的指数是:3但不是原根

模p的所有原根共计2个,列举如下:3 5

与教材结果一致,正确

  1. 教材例5.2.1

题目:教材例5.2.1

输入解释:

依次输入:5 41,分别表示底数a和模数p

输出结果:

模p的欧拉函数是:40

整数a模p的指数是:20但不是原根

模p的所有原根共计16个,列举如下:6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35

与教材结果一致,正确

  1. 教材例5.2.2

题目:

输入解释:

依次输入:9 43,分别表示底数a和模数p

输出结果:

模p的欧拉函数是:42

整数a模p的指数是:21但不是原根

模p的所有原根共计12个,列举如下:3 5 12 18 19 20 26 28 29 30 33 34

与教材结果一致,正确

  1. 测试电脑计算极限

找到素数表,多次输入尝试,发现输入p=46337时是实验电脑能计算的p的最大值,程序运行能在10秒内运算出结果

......(中间结果)

输入下一个更大的素数p=46349会计算不出结果:

六、总结

本次实验用c++编程实现了求解底数a模p的指数和模p的所有原根。在程序前提是p为奇素数的情况下,故先判断前提并且这里调用了c++的库函数__gcd求解最大公因数;进入程序先计算了模p的欧拉函数,这在判断原根时很有用;按照指数的定义编程求解;原根的求解方式有多种,经尝试发现用定义和性质而不是用原根存在性的充要条件会优化许多,因为可以利用之前的欧拉函数结论和再次调用求指数函数,并且时间复杂度也会明显降低。利用求原根还测试了电脑的性能,发现其极限是计算最大奇素数p=46337的原根。

Read More
post @ 2023-12-23

信息安全数学基础

课程实验报告

实验报告(三)

系 别: 网络空间安全系

班 级: secret!

姓 名: secret!

学 号: secret!

实验时间: 2023年10月30日

指导老师: secret!

湖南大学信息科学与工程学院

  1. 实验内容

  1. 实验目标

理解中国剩余定理,用c++实现并不能调用现有库函数,并在优化时增加初始判断条件

  1. 实验原理

  1. 实验设计

实验共分为1个主函数和2个自定义函数。其中,主函数负责部分基本变量定义、判断中国剩余定理判断条件以及输入和输出,chineseRemainder函数是实现中国剩余定理算法核心部分,extEuclidean函数是实现广义欧几里算法用来求解逆元。

  1. 定义变量和函数

主函数:

数组大小:n

存放模的数组:m[]

存放余数的数组:b[]

广义欧几里得系数:s,t

最大公因数:d

chineseRemainder函数:

最终结果:result

所有模的乘积:M

广义欧几里得系数:x,y

中国剩余定理的M:Mi

extEuclidean函数:

函数参数传入的余数:a

函数参数传入的模:b

广义欧几里得系数:x,y

最大公因数:d

  1. 主函数

主函数负责部分基本变量定义、判断中国剩余定理判断条件以及输入和输出

首先定义数组大小n,存放模的数组m,存放余数的数组b,尽量开大一些;

然后输入数组大小n,循环读入模m的元素,循环读入余数b的元素;

判断输入的模是否互素,通过双重for循环遍历模m数组,调用广义欧几里得函数extEuclidean的返回值最大公因数d判断,若存在两两不互素即最大公因数d不为1,则输出错误信息并直接返回程序;

若满足模两两互素,则调用中国剩余定理chineseRemainder函数并输出结果。

  1. chineseRemainder函数

函数是实现中国剩余定理算法核心部分

函数参数传入数组大小n,存放模的数组m,存放余数的数组b;

初始化结果result为0,所有模乘积M为1,定义用于广义欧几里得计算的系数x、y;

循环累乘计算出所有模乘积M,方便后续计算中国剩余定理中的Mi

循环逐个计算每一个同余式的结果并累加到最终结果result,Mi计算为所有模乘积M除以当前模m[i],调用extEuclidean函数利用广义欧几里得求解模m[i]的逆元,得到系数x就是逆元,再利用中国剩余定理累乘b*Mi*x,此时及时对M取模使得结果不会太大超出范围;

将result+模M再取模M 的处理是保证结果result总为正数,理由是在广义欧几里得算出的逆元x没有取正数处理,所以求出的逆元可能是一个负数;

返回最终结果result。

  1. extEuclidean函数

函数是实现广义欧几里算法用来求解逆元

利用递归的思想迭代求解广义欧几里得系数x和y,递归出口是余数b为0;

接受两个参数 a 和 b,表示要计算的两个整数。还接受两个引用参数 x 和 y,用于返回计算结果。

首先检查 b 是否为0。如果是0,说明 a 是最大公约数,此时将 x 设置为1,y 设置为0,并直接返回。

如果 b 不为0,那么函数会递归调用自身,传入参数 b 和 a 除以 b 的余数 a % b,并接收返回的结果 x和 y。

通过递归调用,函数计算出最大公约数d,并将它们存储在传入的引用参数 x 和 y 中,函数迭代y的值并返回最大公因数d

  1. 实验结果
  2. 物不知数

题目:

输入解释:

依次输入:n=3;模m数组:3,5,7;余数b数组:2,3,2

输出结果:

23,与教材结果一致,表示最少有这么多物品

  1. 韩信点兵之二

题目:

输入解释:

依次输入:n=4;模m数组:5,6,7,11;余数b数组:1,5,4,10

输出结果:

2111人,与教材结果一致,表示最少有这么多兵

  1. 作业8

题目:

输入解释:

依次输入:n=5;模m数组:2,3,5,7,11;余数b数组:1,1,1,1,0

输出结果:

2101,经验算:2101/11=191,2101-1=2*3*5*7*10,即2|2101-1,3|2101-1,5|2101-1,7|2101-1

  1. 模不互素的情况

设计最后一个模数只与倒数第二个模数不互素,这样双重for循环判断模是否互素会遍历模m的所有元素,时间是n(n+1)/2。虽然调用extEuclidean函数使用递归实现,但程序反应很快看不出延时

输入解释:

依次输入:n=15;模m数组:99,100,101,97,89,79,73,47,43,23,29,17,19,13,169;余数b数组:15,14,13,12,11,10,9,8,7,6,5,4,3,2,1

输出结果:

模不互素:13和169的最大公因数是13

打印错误信息,表示模之间存在两两不互素情况,没有严格遵守中国剩余定理的使用条件,直接退出程序

六、总结

本次实验在不调用库函数的情况下用c++实现中国剩余定理,利用到实验一中的广义欧几里得算法求解最大公因数判断互素条件以及求解逆元,解决一次同余方程组的求解问题。

Read More
post @ 2023-12-23

信息安全数学基础

课程实验报告

实验报告(二)

系 别: 网络空间安全系

班 级: secret!

姓 名: secret!

学 号: secret!

实验时间: 2023年10月25日

指导老师: secret!

湖南大学信息科学与工程学院

一、实验内容

编程求解模平方计算法

二、实验目标

理解模平方计算法并会用c++编程求解,进一步改进优化

  1. 实验原理

  1. 实验设计

实验共分为主函数和4个自定义函数,

Longlong类型解释:

变量均定义为long long而不是一味的int的原因是,为了解决指数很大的情况,例如老师上课随机举例的日期如20231025等等,进而存放二进制表示的数组也要开大一些

自定义函数解释:

decToBin函数作用是将十进制数转换为二进制数

calcBit函数的作用是计算一个数的二进制位数

printBin函数的作用是打印存储在数组中的二进制数

calMod函数的作用是计算模幂运算

其中最核心的部分是calMod函数,按照模平方算法的思想进行代码实现,并输出时保证计算过程清晰可见

  1. 定义变量和函数

主函数:

long long类型变量:

指数exponent

底数base

二进制位数bit

模mod

二进制表示数组binary[32]

decToBin函数:

long long类型变量:

除2余数i

除2商j

二进制表示数组的下标k

calcBit函数:

long long类型:

十进制整数n

循环变量最终表示二进制位数i

printBin函数:

long long类型:

循环打印变量且为数组下标i

calcMod函数:

long long类型:

算法中的a不断迭代result

算法中的b不断迭代base

数组下标j

  1. 主函数

首先声明了变量exponent、base、bit和mod,以及一个存储二进制数的数组binary[]有32位。然后,函数打印欢迎信息和输入提示信息。接下来,函数使用scanf函数从用户输入中读取指数、底数和模数。然后,函数打印指数的二进制表示,并调用calcBit函数计算二进制位数,并调用printBin函数打印存储的二进制数。最后,函数调用calcMod函数进行模幂运算。函数返回0,表示程序正常结束。

  1. decToBin函数

此函数的作用是将十进制数转换为二进制数。函数参数是一个十进制数n和一个存储二进制数的数组binary[]作为参数。函数使用循环将十进制数n转换为二进制数,并将每一位二进制数存储在数组binary[]中。然后,函数使用循环打印二进制数,并在每4位之间插入一个空格。最后,函数返回0。

  1. calcBit函数

此函数的作用是计算一个数的二进制位数。函数的参数是十进制整数n。函数使用循环逐渐增加一个变量i的值,直到找到一个i,使得2的i次方大于n。然后,函数返回i。

其实还有一种方法,就是遍历已求得的二进制数组,找到最高位为1对应的数组下标,加1就是二进制位数,不同的是函数传参是binary数组而不是十进制整数n

  1. printBin函数

此函数的作用是打印存储在数组中的二进制数。函数的参数是存储二进制数的数组binary[]。函数使用循环打印数组中的每一位二进制数,并在每4位之间插入一个空格。最后,函数返回0。

  1. calMod函数

此函数的作用是计算模幂运算。函数的参数有指数exponent、底数base、模数mod、二进制位数bit和存储二进制数的数组binary[]。函数使用循环根据二进制数的每一位进行模幂运算,并打印每一步的计算过程。最后,函数返回计算结果。

具体的,函数严格模拟了模平方算法整个过程,刚开始令a取1,b取底数;如果二进制当前位为0,那么ai=a(i-1),否则ai=a(i-1)*bi;bi=b(i-1)^2;直到计算完所有二进制位数,输出a的当前结果就是代求的余数结果

  1. 实验结果
  2. 教材2.5.6

计算12996^227(mod37909)

输入:227 12996 37909

输入解释:依次输入指数227、底数12996、模数37909

输出结果解释:

227的二进制表示是1110 0011共8位,倒序存储在数组中(二进制表示的低位对应数组低位),由此可知共循环计算8次,按照模平方算法,最后结果余数为7775。

  1. 作业2.5教材P89 24

计算3^1000000(mod 7)

输入:

1000000 3 7

输入解释:

依次输入指数1000000、底数3、模数7

输出结果解释:

1000000的二进制表示是1111 0100 0010 0100 0000共20位,倒序存储在数组中(二进制表示的低位对应数组低位),由此可知共循环计算20次,按照模平方算法,最后结果余数为5。

  1. 随机出题

计算1234^20231025(mod 56789)

输入:

20231025 1234 56789

输入解释:

依次输入指数20231025、底数1234、模数56789

输出结果解释:

20231025的二进制表示是1 0011 0100 1011 0011 0111 0001共25位,倒序存储在数组中(二进制表示的低位对应数组低位),由此可知共循环计算25次,按照模平方算法,最后结果余数为33926。

六、总结

本次实验用c++编程实现了模平方计算方法。自定义了几个辅助函数用于前期的处理准备,将指数十进制转为二进制,由于指数可能较大,所以用一个数组保存二进制的每一位,值得注意的是,需要倒序把放入数组中方便后续的模平方计算。代码严格按照模平方计算过程模拟实现。如果二进制当前位为0,那么ai=a(i-1),否则ai=a(i-1)*bi;bi=b(i-1)^2;直到计算完所有二进制位数,输出a的当前结果就是代求的余数结果。

Read More
post @ 2023-12-22

关于这个博客的处女作hhh

现在是2023年12月22日 23点56分,咳咳,虽然现在是紧张的考试周,明天就是一年一度的考研了(虽然我现在还是大三还不用考),但是!总之学校周围走到哪都感到沉闷的低气压…
今天在自习室和图书馆看了一天算法设计与分析,准备晚上再看看编译原理,但是我真的好困zzz(虽然下午已经睡过了,但晚上还是好困…是不是暴露了我是INTP哈哈)。
从昨晚到现在终于挤出点时间做自己想做的事情,制作我的第一个网站!!昨晚照着网上“三分钟教程”结果部署了快三小时(我知道我很菜啦!特别是在网络这块…因为上学期网络没学好本能有些畏惧排斥:C)但是无论如何我还是建好啦!精心挑选的我喜欢的主题!
感谢每一位点进来的uu!如果我的博客能给你哪怕一丢丢帮助我都很开心啦!让我们一起进步!加油!计算机er!

Read More
post @ 2023-12-21

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Read More
⬆︎TOP